package Sequence;

public class Test0106 {
    public static void main(String[] args) {
        new Solution0106_1().buildTree(new int[]{10,12,9,11,3,15,20,7},new int[]{12,10,11,9,15,7,20,3});
    }
}

class Solution0106_1 {
    int in;
    int post;
    int[] inorder;
    int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        in=inorder.length-1;
        post=postorder.length-1;
        this.inorder=inorder;
        this.postorder=postorder;

        return build(Integer.MIN_VALUE);
    }

    public TreeNode build(int stop){
        if (post<0)
            return null;

        if (inorder[in]==stop){
            in--;
            return null;
        }

        TreeNode node = new TreeNode(postorder[post--]);
        node.right=build(node.val);
        node.left=build(stop);

        return node;
    }
}

class SolutionTest0106 {
    int inIndex;
    int postIndex;
    int[] inorder;
    int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inIndex=inorder.length-1;
        postIndex=postorder.length-1;
        this.inorder=inorder;
        this.postorder=postorder;

        return build(Integer.MIN_VALUE);
    }

    public TreeNode build(int stop){
        if (postIndex<0) return null;
        if (inorder[inIndex]==stop){
            inIndex--;
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex--]);
        root.right=build(root.val);
        root.left=build(stop);
        return root;
    }
}